#include <stdio.h>
#include <stdbool.h>

#define MaxSize 10 // 双端队列的最大容量

typedef struct
{
    int data[MaxSize]; // 静态数组存储元素
    int front;         // 队头指针
    int rear;          // 队尾指针
} SqDeque;

// 1. 初始化双端队列
void InitDeque(SqDeque &DQ)
{
    DQ.front = 0; // 队头指针初始为0
    DQ.rear = 0;  // 队尾指针初始为0
}

// 2. 销毁双端队列（顺序存储无需特殊操作）
void DestroyDeque(SqDeque &DQ)
{
    DQ.front = DQ.rear = 0;
}

// 3. 队头入队
bool PushFront(SqDeque &DQ, int x)
{
    if ((DQ.front - 1 + MaxSize) % MaxSize == DQ.rear)
    { // 队满判断
        printf("Deque is full!\n");
        return false;
    }
    DQ.front = (DQ.front - 1 + MaxSize) % MaxSize; // 循环前移
    DQ.data[DQ.front] = x;
    return true;
}

// 4. 队尾入队
bool PushRear(SqDeque &DQ, int x)
{
    if ((DQ.rear + 1) % MaxSize == DQ.front)
    { // 队满判断
        printf("Deque is full!\n");
        return false;
    }
    DQ.data[DQ.rear] = x;
    DQ.rear = (DQ.rear + 1) % MaxSize; // 循环后移
    return true;
}

// 5. 队头出队
bool PopFront(SqDeque &DQ, int &x)
{
    if (DQ.front == DQ.rear)
    { // 队空判断
        printf("Deque is empty!\n");
        return false;
    }
    x = DQ.data[DQ.front];
    DQ.front = (DQ.front + 1) % MaxSize; // 循环后移
    return true;
}

// 6. 队尾出队
bool PopRear(SqDeque &DQ, int &x)
{
    if (DQ.front == DQ.rear)
    { // 队空判断
        printf("Deque is empty!\n");
        return false;
    }
    DQ.rear = (DQ.rear - 1 + MaxSize) % MaxSize; // 循环前移
    x = DQ.data[DQ.rear];
    return true;
}

// 7. 获取队头元素
bool GetFront(SqDeque DQ, int &x)
{
    if (DQ.front == DQ.rear)
    {
        printf("Deque is empty!\n");
        return false;
    }
    x = DQ.data[DQ.front];
    return true;
}

// 8. 获取队尾元素
bool GetRear(SqDeque DQ, int &x)
{
    if (DQ.front == DQ.rear)
    {
        printf("Deque is empty!\n");
        return false;
    }
    int rearPos = (DQ.rear - 1 + MaxSize) % MaxSize;
    x = DQ.data[rearPos];
    return true;
}

// 9. 判空操作
bool IsEmpty(SqDeque DQ)
{
    return (DQ.front == DQ.rear);
}

// 10. 判满操作
bool IsFull(SqDeque DQ)
{
    return ((DQ.rear + 1) % MaxSize == DQ.front);
}

// 打印双端队列内容
void PrintDeque(SqDeque DQ)
{
    if (IsEmpty(DQ))
    {
        printf("Deque is empty\n");
        return;
    }

    printf("Deque [front->rear]: ");
    int i = DQ.front;
    while (i != DQ.rear)
    {
        printf("%d ", DQ.data[i]);
        i = (i + 1) % MaxSize;
    }
    printf("\n");
}

int main()
{
    SqDeque DQ;
    InitDeque(DQ); // 初始化双端队列

    // 前端操作
    PushFront(DQ, 10);
    PushFront(DQ, 20);
    printf("After front push: ");
    PrintDeque(DQ); // Deque [front->rear]: 20 10

    // 后端操作
    PushRear(DQ, 30);
    PushRear(DQ, 40);
    printf("After rear push: ");
    PrintDeque(DQ); // Deque [front->rear]: 20 10 30 40

    // 获取队头和队尾
    int front, rear;
    GetFront(DQ, front);
    GetRear(DQ, rear);
    printf("Front: %d, Rear: %d\n", front, rear); // Front: 20, Rear: 40

    // 前端出队
    int poppedFront;
    PopFront(DQ, poppedFront);
    printf("Popped front: %d\n", poppedFront); // Popped front: 20
    PrintDeque(DQ);                            // Deque [front->rear]: 10 30 40

    // 后端出队
    int poppedRear;
    PopRear(DQ, poppedRear);
    printf("Popped rear: %d\n", poppedRear); // Popped rear: 40
    PrintDeque(DQ);                          // Deque [front->rear]: 10 30

    // 判空和判满测试
    printf("Is empty? %s\n", IsEmpty(DQ) ? "true" : "false");
    printf("Is full? %s\n", IsFull(DQ) ? "true" : "false");

    DestroyDeque(DQ); // 销毁双端队列
    return 0;
}